%\vspace{-0.25in}
\section{Grids}
%\vspace{-0.15in}
\label{sec:grid}

We can show $O(n \log n)$ expected cover time of a $d$-dimensional grid quite easily. For simplicity we will first show it for the two-dimensional grid and then generalize to the $d$-dimensional grid.


\begin{lemma}
\label{lem:2dgrid}
Let G be a finite 2-dimensional grid of size $(\sqrt{n} \times \sqrt{n})$. Then the cover-time of a cobra-walk with a branching factor 2 on $G$ is $O(\sqrt{n} \log n)$.
\end{lemma}
\begin{proof}
The proof of this lemma makes use of Matthew's bound for cobra-walks. The longest path in the grid w.r.t hitting time for a cobra-walk is from the point $x = (0,0)$ to (y = $\sqrt{n}, \sqrt{n}$). We need to show that the hitting time of this walk is $O(n)$. To do this, we only need to keep track of the pebble that is closest to $y$ at each step of the walk, where by closest we mean the Manhattan distance.  Let $x'$ be the location of the closest pebble to $y$ at time $t$. Let $A$ be the event that at least one pebble from $x'$ moves closer to $y$. Then:
$\prob{A} = 1 - \prob{\bar{A}} = 1 - (1-p)^k$
, where $p$ is the fraction of edges of $x'$ that lead to vertices closer to $y$ and depends on where in the grid $x'$ is.  If $x'$ is in the interior of $G$, then $p = 1/2$, meaning $\prob{A} > 1/2$ for $k \geq 2$. If $x'$ is on the bottom or left boundary of $G$, $p = 2/3$, and if on the top or right boundary, $p = 1/3$. In either case, for $k \geq 2$, $\prob{A} > 1/2$. Hence, we have a biased random walk on a line, which we know has $O(l)$ cover time. In this case, $l = 2\sqrt{n}$, and thus by applying Matthew's bound we get our desired $O(\sqrt{n} \log n)$ bound.
\end{proof}

\begin{theorem}
\label{the:grid}
Let G be a finite d-dimensional grid for some constant d. Then the cover time of a cobra walk on $G$ is $O(n^{1/d} \log n)$ as long as branching factor $k \geq d$. 
\end{theorem}
\begin{proof}
The proof of this theorem is very similar to that of \ref{lem:2dgrid}. For $G$ the longest path is $d n^{1/d}$, and the key point is that the probability of a cobra-walk from any vertex moving closer to $y$ is even higher than in the 2-d grid, since clearly the worst place to be again is on an "edge" of the grid. When on this edge, the probability of not moving towards y is  $(2d - (d))/(2d - (d -1))^k$. Hence the probability of moving towards $y$ will be greater than $1/2$ only when $k \geq d$.  
\end{proof}
